package com.sicheng.lc.周赛.分类.贪心;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/9 9:36
 */
public class 将数组排序的最少替换次数 {
    //https://leetcode.cn/problems/minimum-replacements-to-sort-the-array/
    //  拆分过程 不可以拆一个更大的数出来
    //  拆完后 数组非降序 并且 最后一个数字最大
    //  最后一个数最大 我们没必要拆最后一个数
    //  假设拆出x个数  nums[i] = v1+v2+...vx
    //  拆出来的每个数  v <= m , m要尽可能大那nums[i-1] 就不会拆的更细
    //  nums[i] <= mx====> x >=ceil(nums[i] / m) = (nums[i] - 1) / m + 1
    //  对nums[i]的操作次数就是 k = x - 1
    //  对新的 m >= nums[i] / x,(nums[i] 被分的尽量均匀 m 就大些)
    public long minimumReplacement(int[] nums) {
        long res = 0;
        int m = nums[nums.length - 1];
        for (int i = nums.length - 1; i > 0; i--) {
            int k = (nums[i] - 1) / m;
            res += k;
            m = nums[i] / (k + 1);
        }
        return res;
    }
}
